#include <bits/stdc++.h>
#include "BinarySearchTree.h"
using namespace std;

int n;
vector <int> data, temp;
int main() {
	ios::sync_with_stdio(false);
	
	cin >> n;
	data.resize(n);
	for(int i = 0; i < n; ++i) cin >> data[i];
	
	double begin, end;
	
	temp = data;
	begin = clock();
	sort(temp.begin(), temp.end());
	end = clock();
	if (n < 1e5) for(int i = 0; i < n; ++i) cout << temp[i] << ' ';
	cout << endl;
	cout << "std::sort: time = " << end - begin << endl;
	
	temp = data;
	begin = clock();
	BST_sort(temp);
	end = clock();
	if (n < 1e5) for(int i = 0; i < n; ++i) cout << temp[i] << ' ';
	cout << endl;
	cout << "BST_sort: time = " << end - begin << endl;
	
	temp = data;
	begin = clock();
	Randomized_BST_sort(temp);
	end = clock();
	if (n < 1e5) for(int i = 0; i < n; ++i) cout << temp[i] << ' ';
	cout << endl;
	cout << "Randomized_BST_sort: time = " << end - begin << endl;
}
